package Practice;

import org.w3c.dom.ls.LSOutput;

import java.util.*;

public class PracticeSolution3 {
    public static void main(String[] args) {
        DinnerPlates dinnerPlates = new DinnerPlates(2);
        dinnerPlates.push(1);
        dinnerPlates.push(2);
        dinnerPlates.push(3);
        dinnerPlates.push(4);
        dinnerPlates.push(5);
        System.out.println(dinnerPlates.popAtStack(0));
        dinnerPlates.push(20);
        dinnerPlates.push(21);
        System.out.println(dinnerPlates.popAtStack(0));
        System.out.println(dinnerPlates.popAtStack(2));
        System.out.println(dinnerPlates.pop());
        System.out.println(dinnerPlates.pop());
        System.out.println(dinnerPlates.pop());
        System.out.println(dinnerPlates.pop());
        System.out.println(dinnerPlates.pop());
        System.out.println(dinnerPlates.pop());
        System.out.println(dinnerPlates.pop());

    }
    static class DinnerPlates {
        private int capacity;
        int index;
        Map<Integer,Integer> map;
        Queue<Integer> queue;

        public DinnerPlates(int capacity) {
            this.capacity = capacity;
            index = 0;
            map = new HashMap<Integer,Integer>();
            queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
                @Override
                public int compare(Integer o1,Integer o2){
                    return o1-o2;
                }
            });
        }

        public void push(int val) {
            int min = index;
            if(!queue.isEmpty()){
                if(min > queue.peek()){
                    min = queue.poll();
                }
            }
            map.put(min,val);
            if(min == index)
                index++;
        }

        public int pop() {
            //if(index == 0) return -1;
            while(index >= 0){
                if(map.containsKey(index)){
                    int ans = map.get(index);
                    map.remove(index);
                    return ans;
                }else{
                    index --;
                }
            }
            index = 0;
            return -1;
        }

        public int popAtStack(int inde) {
            // 计算第inde个stack的最后一个位置
            int pos = inde * capacity + capacity - 1;
            if(pos > index-1){
                return -1;
            }
            for(;pos >= inde*capacity ; pos--){
                if(map.containsKey(pos)){
                    int ans = map.get(pos);
                    queue.offer(pos);
                    map.remove(pos);
                    return ans;
                }
            }
            return -1;
        }
    }
}
